package com.剑指offer一;

/**
 * @ClassName: FindNumberIn2DArray
 * @Description: TODO(剑指 Offer 04. 二维数组中的查找)
 *  在一个 n * m 的二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。
 *  请完成一个高效的函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
 *
 *
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/er-wei-shu-zu-zhong-de-cha-zhao-lcof
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 * @author: li
 * @Date: 2021/12/19 11:30 下午
 */
public class FindNumberIn2DArray {

    public boolean findNumberIn2DArray(int[][] matrix, int target) {
        // 我们可以从左下角开始遍历，规定只有两个方向可以移动，
        // 向上移动，值变小
        // 向右移动，值变大
        if(matrix.length==0){
            return false;
        }
        int n = matrix.length;
        int m = matrix[0].length;
        for (int i = n-1,j=0; i >=0&&j<=m-1 ; ) {
            if(matrix[i][j] == target){
                return true;
            }else if (matrix[i][j]<target){
                j++;
            }else if(matrix[i][j]>target){
                i--;
            }
        }
        return false;
    }
}
